This invention pertains to convolutional coding, with particular but non-exclusive application to telecommunications.
In many environments data in various forms (e.g., various protocols, modulations, etc.) can be transmitted over a channel from a transmitter to a receiver. Depending on the type and circumstances of operation, some channels are more or less prone or susceptible to loss or degradation of the data being transmitted over the channel, with differing channels having differing degrees of potential loss or corruption. For example, a wireline channel typically has a relatively higher degree of integrity and reliability than a channel existing over a radio or interface.
Detection of loss or inaccurate transmission of data over a channel is possible when certain additional information in the form of an error detection code is added to the data stream. For example, at a transmitter a frame or block of data can have appended to it an error detection code in the form of (for example) a check character(s) or check sum which is computed or otherwise derived from the block. Upon reception of the block by the receiver, the receiver can independently recompute or re-derive the error detection code (e.g., the receiver's version of the check character(s) or check sum). If the recomputed or re-derived error detection code (e.g., check sum) is the same as the error detection code included in the received block or frame, the receiver can confirm that the block or frame is correctly decoded.
In addition to error detection techniques, error correcting techniques are also known. For example, error correction codes (generated by polynomials that operate over a frame or block of user data) can also be added to the data stream. Upon reception of the complete frame or block, using the known error correction code/technique the receiver can locate and correct certain errors in the data stream.
A convolutional code is a forward error-correction scheme, whereby the coded sequence is algorithmically achieved through the use of current data bits plus some of the previous data bits from the incoming stream. In telecommunications, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n≧m) and (b) the transformation is a function of the last k information symbols, where k is the constraint length of the code. A trellis description of a convolutional encoder shows how each possible input to the encoder influences both the output and the state transitions of the encoder.
A convolutional code (CC) is called tail-biting (or circular) if the beginning state of its encoding trellis is always equal to the ending state of its encoding trellis after encoding. Tail-biting convolutional codes (TBCC) are simple and powerful forward error correction (FEC) codes, as described, e.g., in H. H. Ma and J. K. Wolf, “On tail biting convolutional codes,” IEEE Trans. Commun., vol. 34, pp. 104-111, February 1986.
Tail-biting convolutional codes (TBCC) are employed in many environments, including telecommunication networks having an air, radio, or “wireless” interface. Tail-biting convolutional codes (TBCC) have been adopted as the mandatory channel codes for the data channels and the overhead channels (like frame control header) in 802.16 WiMAX (Worldwide Interoperability for Microwave Access) system. 802.16 WiMAX is described, e.g., in IEEE Std 802.16-2004, “IEEE Standard for Local and Metropolitan Area Networks—Part 16: Air Interface for Fixed Broadband Wireless Access Systems”, October, 2004; and IEEE Std P802.16e-2005, “IEEE Standard for Local and Metropolitan Area Networks—Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems”, February, 2006, both of which are incorporated herein by reference. They have also been adopted as the channel codes for the header channel in the EDGE system and for the control channel in the IS-54 system. For a description of the EDGE system, see, e.g., M. Mzyece and J. Dunlop, “Performance evaluation of suboptimal decoding schemes for tail biting convolutional codes in EDGE headers,” IEEE Electronics Letters, vol. 39, no. 17, pp. 1280-1281, August 2003, and 3GPP TS 45.003, “3rd Generation Partnership Project; Technical Specification Group GSM/EDGE Radio Access Network; Channel Coding (Release 7)”, V7.1.0, 2007-02, both of which are incorporated herein by reference. For a description of the IS-54 system, see, e.g., R. V. Cox and C.-E. W. Sundberg, “An efficient adaptive circular viterbi algorithm for decoding generalized tail biting convolutional codes,” IEEE Trans. Veh. Technol., vol. 43, pp. 57-68, February 1994, incorporated herein by reference. Further, they have also been adopted for the LTE (Long-Term Evolution) system (See, 3GPP TS 36.212, “3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA); Multiplexing and channel Coding (Release 8)”, V8.0.0, 2007-09, e.g., which is incorporated herein by reference).
Thus, tail biting convolutional codes comprise one class of error correction codes, which adds redundancy bits to the information bits (information bits and redundancy bits together is called one codeword) for error correction. At a receiver, the decoder can try to correct the corrupted bits (if errors happen during the transmission) with the help from the redundancy bits (or the information bits together). For example, if payload (information bits) size is K=6 bits and the coding rate is ⅓, then the length of the codeword is 6*3=18 bits and actually 18−6=12 redundancy bits are added to the 6 information bits. There are in total 2^6=64 different codewords, corresponding to the 64 possible length-6 information bit vectors (from (0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 1), . . . , to (1, 1, 1, 1, 1, 1)).
The encoder structure of a rate 1/n feedforward convolutional code (CC) with overall constraint length v is shown in FIG. 1, where the content consisting of zeros and ones of the v number of shift-register elements is called the state of the encoder. The n number of generator polynomials specify the connections from the shift-registers to the n outputs. The n number of generator polynomials are represented by the set G=(g0, . . . , gn-1), where g0=(g0(0), g0(1), . . . , g0(v)), . . . , gn-1=(gn-1(0), gn-1(1), . . . , gn-1(v)). The coefficients gk(j), for k=0, . . . , n−1 and j=0, . . . , v, is either 0 (no connection) or 1 (with connection). Ui is the input bit at time i, and (vi(0), . . . , vi(n-1)) are the n output bits at time i. Thus, a convolutional code can be specified by its set of generator polynomials G=(g0, . . . , gn-1).
A convolutional code (CC) is called tail-biting (or circular) if the beginning state of its encoding trellis is always equal to the ending state of its encoding trellis after encoding. For a feedforward CC, the beginning state is simply determined by the last v number of input bits, where v is the overall constraint length. For a feedback convolutional code (CC), the encoder structure has to comply with certain conditions so that the circular encoding is possible. In both cases (feedforward and feedback CC) the beginning state (also called the circular state) of the encoding trellis is determined from the input information bit vector. That is, the beginning state is not always equal to the all-zero state and depends on the values of the input bits. On the other hand, in the conventional zero-tail convolutional codes (ZTCC), the beginning state and the ending state are always equal to the all-zero state, and v number of redundant zero-tail bits are needed to return the encoder to the all-zero state.
An example encoder for the 802.16 Tail-biting convolutional codes (TBCC) is shown in FIG. 2. The encoder has code rate 1/n=½, constraint length v=6, and G=(g0,g1), where g0=(1, 1, 1, 1, 0, 0, 1) and g1=(1, 0, 1, 1, 0, 1, 1). In other words, the adder Ag0 for the first polynomial g0 is connected to receive the bit values from the first through fourth positions and the seventh position of the shift register chain of FIG. 2 (e.g., the first position being the input to shift register Ui-1; the second position being the output of shift register Ui-2; the third position being the output of shift register Ui-3; and so on to the seventh position being the output of shift register Ui-6). The adder Ag1 for the second polynomial g1 is connected to receive the bit values from the first, third, fourth, sixth, and seventh positions of the shift register chain of FIG. 2.
To represent the generator polynomials in a more compact way, the octal notation is usually used, where zeros (0) are appended on the right of the binary notation to make the total number of digits a multiple of 3. For example, two zeroes are appended to the right of g0 to generate the binary vector g0′=(1, 1, 1, 1, 0, 0, 1, 0, 0). Then the digits in g0′ are grouped with 3 digits per group and the result is g0″=(111, 100, 100). Finally each group in g0″ is transformed to its equivalent octal notation and the result is (7, 4, 4). The generator polynomials depicted in FIG. 2 for the 802.16 TBCC in octal notation are thus given by G=(744, 554). The more compact octal notation is typically used herein to represent the generator polynomials.
There are many advantages of using Tail-biting convolutional codes (TBCC) over the conventional zero-tail convolutional codes (ZTCC) and some block codes. Two example advantages are listed below:
Advantage 1. zero-tail convolutional codes (ZTCC) need to use v number of redundant zero-tail bits to terminate the encoding trellises to the all-zero state. In Tail-biting convolutional codes (TBCC), zero-tail bits are not needed and they can be replaced by payload bits to increase the spectral efficiency of the channel code.
Advantage 2. Many good block codes can be generated by equivalent Tail-biting convolutional codes (TBCC), and hence can be decoded by the more efficient soft-input soft-output decoding algorithms for trellis codes.
Performances of convolutional codes (CC) are determined by the generator polynomials and the resulting weight spectrum, and the constructions of convolutional codes (CC) with good weight spectrum are usually done by extensive computer searches (as described, e.g., in references [2]-[9], listed hereinafter).
The weight spectrum (or distance spectrum) of a code C is defined by Expression 1.WS(C)={(d,nd,bd):d=df,df+1, . . . }  Expression 1In Expression 1, df is the free distance (or the minimum distance dmin), nd is the number of codewords with weight d, and bd is the total number of nonzero information bits associated with codewords with weight d. Each triple (d, nd, bd) is called a line in the weight spectrum. If a convolutional code (CC) does not have a weight-d1 codeword, then the corresponding line (d1, nd1, bd1) does not exist.
The performances of convolutional codes (CC) are characterized either by the decoder frame error rate (FER) or the bit error rate (BER). It can be shown that, for a rate R=1/n Tail-biting convolutional codes (TBCC) with payload size K bits, the frame error rate (FER) and bit error rate (BER) can be upper bounded by Expression 2 and Expression 3.
                              P                      F            ,            UB                          =                              ∑                          d              ≥              df                                ⁢                                    n              d                        ·                          Q              ⁡                              (                                                      2                    ·                    d                    ·                    R                    ·                                          (                                                                        E                          b                                                /                                                  N                          0                                                                    )                                                                      )                                                                        Expression        ⁢                                  ⁢        2                                          P                      B            ,            UB                          =                              1            K                    ·                                    ∑                              d                ≥                df                                      ⁢                                          b                d                            ·                              Q                ⁡                                  (                                                            2                      ·                      d                      ·                      R                      ·                                              (                                                                              E                            b                                                    /                                                      N                            0                                                                          )                                                                              )                                                                                        Expression        ⁢                                  ⁢        3            In the foregoing,
      Q    ⁡          (      x      )        =            ∫      x      ∞        ⁢                  1                              2            ⁢            π                              ⁢                          ⁢              exp        ⁡                  (                                    -                              z                2                                      /            2                    )                    ⁢              ⅆ        z            is the well-know Q-function. Eb/N0 is the energy per bit to the noise power spectral density ratio. Eb/N0 is used herein as the definition for signal to noise ratio (SNR). As can be seen from the above Expressions, the upper bound on the FER of a convolutional code (CC) can be reduced by minimizing the “multiplicity” nd, and the upper bound on the BER can be reduced by minimizing the “bit multiplicity” bd.
The search criteria for good convolutional codes (CC) can be roughly divided into the following two categories:
Category 1: Maximum Free Distance (MFD) Codes: The rule of thumb for finding good convolutional codes (CC) is to first find generator polynomials which will result in the maximum free distance (MFD) df and the codes generated are called MFD codes (See, reference [2], listed hereinafter). If multiple generator polynomials have the same df, then the ones with minimum nd (or bd) are selected and they are called MFD-FER codes (or MFD-BER codes). MFD codes are useful when the Eb/N0 value is so large (i.e., over the very high SNR region) that only the df term (the first line in the weight spectrum) has a significant contribution to PF,UB (or PB,UB).
Category 2: ODS (Optimum Distance Spectrum) Codes: A Convolutional Code (CC) C with weight spectrum WS(C)={(d, nd, bd): d=df, df+1, . . . } has a superior FER (or BER (See, reference [4], listed hereinafter)) distance spectrum than that of a Convolutional Code (CC) C with weight spectrum WS(C)={(d, nd, bd): d=df, df+1, . . . } if one of the conditions of Expression 4 or Expression 5 is satisfied.df>df or  Expression 4df=df  Expression 5and there exists an integer j>1 such that nd=nd for d=df, df+1, . . . , df+j−1 and nd<nd for d=df+j (or bd=bd for d=df, df+1, . . . , df+j−1 and bd<bd for d=df+j).
A Convolutional Code (CC) C is called ODS-FER code (or ODS-BER code) if it has a superior FER (or BER) distance spectrum than another code with the same code rate R and overall constraint length v.
From the above definitions it can be seen that an ODS code is always an MFD code, but not vice versa. For example, two MFD codes C and C with the same (df, ndf, bdf) may have quite different lines (d, nd, bd) for d>df, and have different performances. Therefore, from the performance perspective, the ODS criterion should be used to find good convolutional codes (CC).
For zero-tail convolutional codes (ZTCC), the code searches have been extensively studied before. For example, generator polynomials for some MFD ZTCC are reported in reference [2], listed hereinafter, and the generator polynomials for some ODS-BER ZTCC are reported in references [3], [4] and [9], listed hereinafter.
Due to different encoding structures, the weight spectrums of Tail-biting convolutional codes (TBCC) are usually very different than those of zero-tail convolutional codes (ZTCC) with the same generator polynomials, especially for short and medium-length encoder packets. Moreover, for short and medium-length encoder packets, the optimum generator polynomials (for either the MFD or the ODS criterion) will usually be different for different encoder packet lengths (See, e.g., references [8] and [9]). That is, the optimization (or selection) of the Tail-biting convolutional codes (TBCC) generator polynomials needs to be done for each packet length. For example, generator polynomials for some MFD-FER TBCC codes have been reported (see references [5], [8] and [9], listed hereinafter). For long encoder packets (typically over 30 or 40 bits), the weight spectrums of Tail-biting convolutional codes (TBCC) and zero-tail convolutional codes (ZTCC) with the same generator polynomials will become approximately the same, and generator polynomials optimized for zero-tail convolutional codes (ZTCC) may be directly used for Tail-biting convolutional codes (TBCC) without performance degradation.
There are problems with the selection of the generator polynomials for Tail-biting convolutional codes (TBCC) as currently used. Two general problems are briefly described below:
Problem (1): Tail-biting convolutional codes (TBCC) are used by major wireless systems like EDGE, WiMAX and LTE. However, the generator polynomials of TBCC used by these systems are taken from the MFD zero-tail convolutional codes (ZTCC) or ODS zero-tail convolutional codes (ZTCC) and are not the optimum ones for Tail-biting convolutional codes (TBCC). This is mainly due to the unavailability of Tail-biting convolutional codes (TBCC) search results at the time when the corresponding standards were written. For LTE and EDGE systems, the impacts on performances by not using generator polynomials optimized for Tail-biting convolutional codes (TBCC) are very limited since the payload sizes used in these systems are relatively large. For WiMAX, since short payload sizes (12 bits or 24 bits) are used, performance degradations have been shown to be between 0.5 dB to 1 dB over the additive white Gaussian noise (AWGN) channel, and between 1 dB to 3.7 dB over the multipath fading channels.
Problem (2): The current available search results for the optimum generator polynomials for Tail-biting convolutional codes (TBCC) are MFD codes (See, references [5] [8] and [9], listed hereinafter). From the above discussions, it is now understood that ODS codes should be used instead.